package com.kevin.learn.leetcode;

import com.kevin.learn.domain.TreeNode;

/**
 * 230
 */
public class 二叉搜索树中第K小的元素 {

    public static void main(String[] args) {
        TreeNode treeNode = initData();
        System.out.println(kthSmallest(treeNode,3));
    }

    private static int kthSmallest(TreeNode root, int k) {
        // 利用 BST 的中序遍历特性
        traverse(root, k);
        return res;
    }

    // 记录结果
    private static int res = 0;
    // 记录当前元素的排名
    private static int rank = 0;

    private static void traverse(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        traverse(root.left, k);
        /* 中序遍历代码位置 */
        rank++;
        if (k == rank) {
            // 找到第 k 小的元素
            res = root.data;
            return;
        }
        /*****************/
        traverse(root.right, k);
    }

    private static TreeNode initData() {
        TreeNode treeNode5 = new TreeNode(5);

        TreeNode t3 = new TreeNode(3);
        TreeNode t2 = new TreeNode(2);
        t2.setLeft(new TreeNode(1));
        t3.setLeft(t2);
        TreeNode t4 = new TreeNode(4);
        t3.setRight(t4);
        treeNode5.setLeft(t3);

        TreeNode t6 = new TreeNode(6);
        treeNode5.setRight(t6);
        return treeNode5;
    }
}
